Search Results

Documents authored by Schuster, Peter

Document
DOI: 10.4230/LIPIcs.CSL.2024.16
A General Constructive Form of Higman’s Lemma

Authors: Stefano Berardi, Gabriele Buriola, and Peter Schuster

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
In logic and computer science one often needs to constructivize a theorem ∀ f ∃ g.P(f,g), stating that for every infinite sequence f there is an infinite sequence g such that P(f,g). Here P is a computable predicate but g is not necessarily computable from f. In this paper we propose the following constructive version of ∀ f ∃ g.P(f,g): for every f there is a "long enough" finite prefix g₀ of g such that P(f,g₀), where "long enough" is expressed by membership to a bar which is a free parameter of the constructive version. Our approach with bars generalises the approaches to Higman’s lemma undertaken by Coquand-Fridlender, Murthy-Russell and Schwichtenberg-Seisenberger-Wiesnet. As a first test for our bar technique, we sketch a constructive theory of well-quasi orders. This includes yet another constructive version of Higman’s lemma: that every infinite sequence of words has an infinite ascending subsequence. As compared with the previous constructive versions of Higman’s lemma, our constructive proofs are closer to the original classical proofs.
Cite as

Stefano Berardi, Gabriele Buriola, and Peter Schuster. A General Constructive Form of Higman’s Lemma. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berardi_et_al:LIPIcs.CSL.2024.16,
  author =	{Berardi, Stefano and Buriola, Gabriele and Schuster, Peter},
  title =	{{A General Constructive Form of Higman’s Lemma}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.16},
  URN =		{urn:nbn:de:0030-drops-196599},
  doi =		{10.4230/LIPIcs.CSL.2024.16},
  annote =	{Keywords: intuitionistic logic, constructive mathematics, formal proof, inductive predicate, bar induction, well quasi-order, Higman’s lemma}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2265
Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis

Authors: Hannes Diener and Peter Schuster

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We extract a quantitative variant of uniqueness from the usual hypotheses of the implicit functions theorem. This leads not only to an a priori proof of continuity, but also to an alternative, fully constructive existence proof.
Cite as

Hannes Diener and Peter Schuster. Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 131-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{diener_et_al:OASIcs.CCA.2009.2265,
  author =	{Diener, Hannes and Schuster, Peter},
  title =	{{Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{131--140},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2265},
  URN =		{urn:nbn:de:0030-drops-22651},
  doi =		{10.4230/OASIcs.CCA.2009.2265},
  annote =	{Keywords: Implicit function, uniqueness, continuity, constructive analysis, countable choice}
}
Document
DOI: 10.4230/DagSemProc.05021.4
A Nilregular Element Property

Authors: Thierry Coquand, Henri Lombardi, and Peter Schuster

Published in: Dagstuhl Seminar Proceedings, Volume 5021, Mathematics, Algorithms, Proofs (2006)

Abstract
An element or an ideal of a commutative ring is nilregular if and only if it is regular modulo the nilradical. We prove that if the ring is Noetherian, then every nilregular ideal contains a nilregular element. In constructive mathematics, this proof can then be seen as an algorithm to produce nilregular elements of nilregular ideals whenever the ring is coherent, Noetherian, and discrete. As an application, we give a constructive proof of the Eisenbud--Evans--Storch theorem that every algebraic set in $n$--dimensional affine space is the intersection of $n$ hypersurfaces. The input of the algorithm is an arbitrary finite list of polynomials, which need not arrive in a special form such as a Gr"obner basis. We dispense with prime ideals when defining concepts or carrying out proofs.
Cite as

Thierry Coquand, Henri Lombardi, and Peter Schuster. A Nilregular Element Property. In Mathematics, Algorithms, Proofs. Dagstuhl Seminar Proceedings, Volume 5021, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{coquand_et_al:DagSemProc.05021.4,
  author =	{Coquand, Thierry and Lombardi, Henri and Schuster, Peter},
  title =	{{A Nilregular Element Property}},
  booktitle =	{Mathematics, Algorithms, Proofs},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5021},
  editor =	{Thierry Coquand and Henri Lombardi and Marie-Fran\c{c}oise Roy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05021.4},
  URN =		{urn:nbn:de:0030-drops-2784},
  doi =		{10.4230/DagSemProc.05021.4},
  annote =	{Keywords: Lists of generators, polynomial ideals, Krull dimension, Zariski topology, commutative Noetherian rings, constructive algebra}
}
Document
DOI: 10.4230/DagSemProc.04351.9
Compactness in apartness spaces?

Authors: Douglas Bridges, Hajime Ishihara, Peter Schuster, and Luminita S. Vita

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
A major problem in the constructive theory of apartness spaces is that of finding a good notion of compactness. Such a notion should (i) reduce to ``complete plus totally bounded'' for uniform spaces and (ii) classically be equivalent to the usual Heine-Borel-Lebesgue property for the apartness topology. The constructive counterpart of the smallest uniform structure compatible with a given apartness, while not constructively a uniform structure, offers a possible solution to the compactness-definition problem. That counterpart turns out to be interesting in its own right, and reveals some additional properties of an apartness that may have uses elsewhere in the theory.
Cite as

Douglas Bridges, Hajime Ishihara, Peter Schuster, and Luminita S. Vita. Compactness in apartness spaces?. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{bridges_et_al:DagSemProc.04351.9,
  author =	{Bridges, Douglas and Ishihara, Hajime and Schuster, Peter and Vita, Luminita S.},
  title =	{{Compactness in apartness spaces?}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.9},
  URN =		{urn:nbn:de:0030-drops-1175},
  doi =		{10.4230/DagSemProc.04351.9},
  annote =	{Keywords: Apartness , constructive , compact uniform space}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact